package cn.idu.ismik;

public class S001Dp {


    public static void main(String[] args) {
        S001Dp dp = new S001Dp();
        System.out.println("fib(10)=" + dp.fib1(10));
        System.out.println("fib(10)=" + dp.fib2(10));
        System.out.println("fib(10)=" + dp.fib3(10));
        System.out.println("fib(10)=" + dp.fib4(10));

        int prices[] = {1, 5, 8, 9, 10, 17, 17, 20, 24, 30};
        System.out.println("serling(4)=" + dp.serling1(prices, 4));
        System.out.println("serling(4)=" + dp.serling2(prices, 4));


    }


    //递归斐波那契
    public int fib1(int i) {
        if (i <= 0) return 0;
        if (i == 1) return 1;
        return fib1(i - 1) + fib1(i - 2);
    }


    //自顶向下备忘录法
    public int fib2(int i) {
        if (i <= 0) return 0;
        int[] helpArr = new int[i + 1];
        return fib2Help(i, helpArr);
    }

    private int fib2Help(int i, int[] helpArr) {
        if (i <= 0) return 0;
        if (i == 1) return 1;
        if (helpArr[i] == 0)
            helpArr[i] = fib2Help(i - 1, helpArr) + fib2Help(i - 2, helpArr);
        return helpArr[i];
    }

    //自底向上备忘录法
    public int fib3(int i) {
        if (i <= 0) return 0;
        if (i == 1) return 1;
        int[] helpArr = new int[i + 1];
        helpArr[0] = 0;
        helpArr[1] = 1;

        for (int j = 2; j <= i; j++) {
            helpArr[j] = helpArr[j - 1] + helpArr[j - 2];
        }

        return helpArr[i];
    }

    //自底向上备忘录法-优化空间复杂度为O(1):状态压缩
    public int fib4(int i) {
        if (i <= 0) return 0;
        if (i == 1) return 1;
        int helpIndex_1 = 0;
        int helpIndex_2 = 1;
        int helpIndex_last = 1;

        for (int j = 2; j <= i; j++) {
            helpIndex_last = helpIndex_1 + helpIndex_2;
            helpIndex_1 = helpIndex_2;
            helpIndex_2 = helpIndex_last;
        }

        return helpIndex_last;
    }

    /**
     * 钢条切割问题
     * n={1-10}
     *
     * @param prices 分段钢条价格
     * @param n      原始钢条长度
     * @return 价值最高的分段售价
     */
    //递归方式求解，钢条遍历根据长度进行拆分，分别再求拆分后的最大值（拆之前跟拆之后比）
    //问题终点：不可拆分项,n=1,return maxPrice=prices[0]
    public int serling1(int[] prices, int n) {
        if (n <= 0) return 0;           //边界条件不计算
        if (n == 1) return prices[0];   //终点条件，不可拆分时
        int maxPrice = Integer.MIN_VALUE;
        for (int i = 1; i < n; i++) {
            maxPrice = Math.max(maxPrice, prices[i - 1] + serling1(prices, n - i));
        }
        return maxPrice;
    }


    //备忘录求解，增加空间复杂度，解决计算冗余
    public int serling2(int[] prices, int n) {
        int[] memArr = new int[n];

        memArr[0] = prices[0];
        serling2Help(prices, n, memArr);

        return memArr[n - 1];
    }

    public int serling2Help(int[] prices, int n, int[] memArr) {
        if (n <= 0) return 0;           //边界条件不计算
        if (n == 1) return memArr[0];   //终点条件，不可拆分时

        if (memArr[n - 1] == 0)
            for (int i = 1; i < n; i++) {
                memArr[n - 1] = Math.max(memArr[n - 1], prices[i - 1] + serling2Help(prices, n - i, memArr));
            }

        return memArr[n-1];

    }

}
